﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Queues;
using Algoritmia.Utils;

namespace Algoritmia.Problems.RegularExpressions
{
    public class RegularExpressionParser
    {
        private readonly Func<ILifo<char>> _createLifo;
        private readonly Func<ILifo<RegExpTree>> _createTreesLifo;

        public RegularExpressionParser(Func<ILifo<char>> createLifo = null,
                                       Func<ILifo<RegExpTree>> createTreesLifo = null)
        {
            _createLifo = createLifo ?? (() => AlgoritmiaFactory.Lifos<char>.Default);
            _createTreesLifo = createTreesLifo ?? (() => AlgoritmiaFactory.Lifos<RegExpTree>.Default);
        }

        public IEnumerable<char> Tokenize(string expression)
        {
            char p = default(char);
            var previousDelimiters = new [] {default(char), '(', '|'};
            var lastDelimiters = new[] {')', '|', '*'};
            foreach(var c in expression.Replace(" ",""))
            {
                if ( !previousDelimiters.Contains(p) && !lastDelimiters.Contains(c))
                {
                    yield return '·';
                }
                yield return c;
                p = c;
            }
        }

        public RegExpTree Parse(string expression)
        {
            var operatorsStack = _createLifo();
            var treeStack = _createTreesLifo();
            var operators = new Dictionary<char, int>();
            operators['|'] = 0;
            operators['·'] = 1;
            foreach(var token in Tokenize(expression))
            {
                if ( !"·|*()".Contains(token))
                {
                   treeStack.Push(new RegExpTree(token.ToString()));
                }
                else if ( operators.ContainsKey(token))
                {
                    while (operatorsStack.Count > 0 && operators.ContainsKey(operatorsStack.Top()) && operators[token] <= operators[operatorsStack.Top()])
                    {
                        var last = treeStack.Pop();
                        var previous = treeStack.Pop();
                        treeStack.Push(new RegExpTree(operatorsStack.Pop().ToString(), previous, last));
                    }
                    operatorsStack.Push(token);
                }
                else if (token == '*')
                {
                    treeStack.Push(new RegExpTree("*", treeStack.Pop()));
                }
                else if (token == '(')
                {
                    operatorsStack.Push('(');
                }
                else if (token == ')')
                {
                    while (operatorsStack.Top() != '(')
                    {
                        var last = treeStack.Pop();
                        var previous = treeStack.Pop();
                        treeStack.Push(new RegExpTree(operatorsStack.Pop().ToString(), previous, last));
                    }
                    operatorsStack.Pop();
                }
            }
            while ( operatorsStack.Count > 0)
            {
                var last = treeStack.Pop();
                var previous = treeStack.Pop();
                treeStack.Push(new RegExpTree(operatorsStack.Pop().ToString(), previous, last));
            }

            return treeStack.Top();
        }
    }
}
